package com.lin.searchinsert;

/**
 * @author 九分石人
 */
public class SearchInsert {

    /**
     * 搜索插入位置
     * 要求二分法
     *
     * @param nums   数组
     * @param target 目标数字
     * @return 位置
     */
    public static int search(int[] nums, int min, int max, int target) {
        if (target > nums[max]) {
            return max + 1;
        }
        if (target < nums[min]) {
            return min;
        }
        int mid = (min + max) / 2;

        if (mid == min && nums[min] < target && nums[max] > target) {
            return mid + 1;
        }
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return search(nums, mid + 1, max, target);
        } else if (nums[mid] > target) {
            return search(nums, min, mid - 1, target);
        }
        return mid;
    }

    public static int searchInsert(int[] nums, int target) {
        return search(nums, 0, nums.length - 1, target);
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 8};
        int target = 2;
        int i = searchInsert(nums, target);
        System.out.println(i);
    }
}
